搜狐集团2018秋季校招笔试题（技术类）-编程题二

发表于 | 分类于 ，

题目

描述

工厂生产的产品包装在相同高度 h,尺寸为1*1,2*2,3*3,4*4,5*5,6*6 的方形包装中.
这些产品始终以与产品高度相同的尺寸为 6*6 的包裹交付给客户.
因为邮费很贵,所以工厂要想方设法地减少每个订单运送时的包裹数量.
他们很需要有一个好的程序员帮他们解决这个问题从而节省费用.
现在这个程序由你来设计.

输入

输入文件包括几行,每一行代表一个订单.
每个订单里的一行包括六个整数,中间用空格隔开,分别为 1*1 至 6*6 这六种产品的数量.
输入文件将以 6 个 0 组成一行结尾.

输出

除了输入的最后一行 6 个 0 以外,输入文件里每一行对应着输出文件一行,每一行输出一个整数代表对应订单所需的最小包裹数.

Example

Input

0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0

Output

2
1

题解

直接求解

由于数据量不大,直接求解

  • 1 个 6*6 的产品单独组成一个包裹
  • 1 个 55 的产品可以和 11 个 11 的产品组成一个包裹
  • 1 个 44 的产品可以和 22 或 1*1 的产品组成一个包裹
  • 4 个 33 的产品单独组成一个包裹,若 33 的产品不足 4 个,则可以和 22 的产品或者 11 的产品或者两者混合组成一个包裹
  • 9 个 22 的产品单独组成一个包裹,若 22 的产品不足9个,则可以和1*1的产品组成一个包裹
  • 36 个 1*1 的产品单独组成一个包裹
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>

using namespace std;


int main(int argc, const char * argv[])
{
    int prod[6],c,rest2[4]={0,5,3,1},t;
    while(1)
    {
        scanf("%d%d%d%d%d%d",&prod[0],&prod[1],&prod[2],&prod[3],&prod[4],&prod[5]);
        if(prod[0]|prod[1]|prod[2]|prod[3]|prod[4]|prod[5])
        {
            c=0;
            c+=prod[5];
            cout<<"6 "<<c<<endl;
            c+=prod[4];
            prod[0]-=min(prod[0],prod[4]*11);
            cout<<"5 "<<c<<endl;
            c+=prod[3];
            prod[0]-=min(prod[0],max(0,prod[3]*5-prod[1])*4);
            prod[1]-=min(prod[1],prod[3]*5);
            cout<<"4 "<<c<<endl;
            t=prod[2]/4;
            prod[2]-=4*t;
            c+=t;
            if(prod[2])++c;
            prod[0]-=min(prod[0],36-9*prod[2]-4*min(rest2[prod[2]],prod[1]));
            prod[1]-=min(rest2[prod[2]],prod[1]);
            cout<<"3 "<<c<<endl;
            t=prod[1]/9;
            prod[1]-=9*t;
            c+=t;
            if(prod[1])++c;
            prod[0]-=min(prod[0],36-4*prod[1]);
            cout<<"2 "<<c<<endl;
            c+=prod[0]/36;
            if(prod[0])++c;
            cout<<c<<endl;
        }
        else
            break;
    }
}